\section{\Stack}
\label{sec:stack}
\myindex{\Stack}

La pile est une des structures de données les plus fondamentales en informatique.
\footnote{\href{http://go.yurichev.com/17119}{wikipedia.org/wiki/Call\_stack}}.
\ac{AKA} \ac{LIFO}.

Techniquement, il s'agit d'un bloc de mémoire présent dans l'espace d'adressage
d'un processus et qui est utilisé par le registre \ESP ou \RSP en x86 ou x64,
ou par le registre \ac{SP} en ARM comme un pointeur dans ce bloc mémoire.

\myindex{ARM!\Instructions!PUSH}
\myindex{ARM!\Instructions!POP}
\myindex{x86!\Instructions!PUSH}
\myindex{x86!\Instructions!POP}
Les instructions d'accès à la pile sont \PUSH et \POP (en x86 ainsi qu'en ARM Thumb-mode).
\PUSH soustrait à \ESP/\RSP/\ac{SP} 4 en mode 32-bit (ou 8 en mode 64-bit) et écrit
ensuite le contenu de l'opérande associée à l'adresse mémoire pointée par \ESP/\RSP/\ac{SP}.

\POP est l'operation inverse: elle récupére la donnée depuis l'adresse mémoire pointée par \ac{SP},
l'écrit dans l'opérande associée (souvent un registre) puis ajoute 4 (ou 8) au \glslink{stack pointer}{pointeur de pile}.

Après une allocation sur la pile, le \glslink{stack pointer}{pointeur de pile} pointe sur le bas de la pile.
\PUSH décrémente le \gls{stack pointer} et \POP l'incrémente.

Le bas de la pile représente en réalité le début de la mémoire allouée pour
 le bloc de pile. Cela semble étrange, mais c'est comme ça.

ARM supporte à la fois les piles ascendantes et descendantes.

\myindex{ARM!\Instructions!STMFD}
\myindex{ARM!\Instructions!LDMFD}
\myindex{ARM!\Instructions!STMED}
\myindex{ARM!\Instructions!LDMED}
\myindex{ARM!\Instructions!STMFA}
\myindex{ARM!\Instructions!LDMFA}
\myindex{ARM!\Instructions!STMEA}
\myindex{ARM!\Instructions!LDMEA}

Par exemple les instructions \ac{STMFD}/\ac{LDMFD}, \ac{STMED}/\ac{LDMED} sont utilisées pour gérer les piles
descendantes (qui grandissent vers le bas en commençant avec une adresse haute et évoluent vers une plus basse).

Les instructions \ac{STMFA}/\ac{LDMFA}, \ac{STMEA}/\ac{LDMEA} sont utilisées pour gérer les piles montantes
(qui grandissent vers les adresses hautes de l'adresse space, en commençant avec une adresse située en bas de l'adresse space)

% It might be worth mentioning that STMED and STMEA write first,
% and then move the pointer,
% and that LDMED and LDMEA move the pointer first, and then read.
% In other words, ARM not only lets the stack grow in a non-standard direction,
% but also in a non-standard order.
% Maybe this can be in the glossary, which would explain why E stands for "empty".

\subsection{Pourquoi la pile grandit en descendant ?}
\label{stack_grow_backwards}

Intuitivement, on pourrait penser que la pile grandit vers le haut, i.e. vers des
adresses plus élevées, comme n'importe qu'elle autre structure de données.

La raison pour laquelle la pile grandit vers le bas est probablement historique.
Dans le passé, les ordinateurs étaient énormes et occupaient des pièces entières,
il était facile de diviser la mémoire en deux parties, une pour le \gls{heap} et
une pour la pile.
Evidemment, on ignorait quelle serait la taille du \gls{heap} et de la pile durant
l'exécution du programme, donc cette solution était la plus simple possible.

\input{patterns/02_stack/stack_and_heap}

Dans \RitchieThompsonUNIX on peut lire:

\begin{framed}
\begin{quotation}
The user-core part of an image is divided into three logical segments. The program text segment begins at location 0 in the virtual address space. During execution, this segment is write-protected and a single copy of it is shared among all processes executing the same program. At the first 8K byte boundary above the program text segment in the virtual address space begins a nonshared, writable data segment, the size of which may be extended by a system call. Starting at the highest address in the virtual address space is a pile segment, which automatically grows downward as the hardware's pile pointer fluctuates.
\end{quotation}
\end{framed}

Cela nous rappelle comment certains étudiants prennent des notes pour deux cours différents dans
un seul et même cahier en prenant un cours d'un côté du cahier, et l'autre cours de l'autre côté.
Les notes de cours finissent par se rencontrer à un moment dans le cahier quand il n'y a plus de place.

% I think if we want to expand on this analogy,
% one might remember that the line number increases as as you go down a page.
% So when you decrease the address when pushing to the stack, visually,
% the stack does grow upwards.
% Of course, the problem is that in most human languages,
% just as with computers,
% we write downwards, so this direction is what makes buffer overflows so messy.

\subsection{Quel est le rôle de la pile ?}

% subsections
\input{patterns/02_stack/01_saving_ret_addr_FR}
\input{patterns/02_stack/02_args_passing_FR}
\input{patterns/02_stack/03_local_vars_FR}
\input{patterns/02_stack/04_alloca/main}
\input{patterns/02_stack/05_SEH}
\input{patterns/02_stack/06_BO_protection}

\subsubsection{Désallocation automatique de données dans la pile}

Peut-être que la raison pour laquelle les variables locales et les enregistrements SEH sont stockés dans la
pile est qu'ils sont automatiquement libérés quand la fonction se termine en utilisant simplement une
instruction pour corriger la position du pointeur de pile (souvent \ADD).
Les arguments de fonction sont aussi désalloués automatiquement à la fin de la fonction.
À l'inverse, toutes les données allouées sur le \IT{heap} doivent être désallouées de façon explicite.

% sections
\input{patterns/02_stack/07_layout_FR} % TBT
\input{patterns/02_stack/08_noise/main}
\input{patterns/02_stack/exercises}
